﻿ #define _CRT_SECURE_NO_WARNINGS 1

//字符串栈的最大空间数
#deﬁne L_MAX_SIZE 10000
//数字栈的最大空间数
#deﬁne N_MAX_SIZE 100
//反转字符串
void reverse(char* str)
{
	int len = strlen(str);
	for (int i = 0, j = len - 1; i < j; i++, j--)
	{
		char tmp = str[i];
		str[i] = str[j];
		str[j] = tmp;
	}
}
char* decodeString(char* s)
{
	int nTop = -1, lTop = -1;
	char lStack[L_MAX_SIZE] = ""; //字符串栈
	int nStack[N_MAX_SIZE] = { 0 }; //数字栈
	int numTmp = 0; //存储左括号[的左边数字
	for (int i = 0; i < strlen(s); i++)
	{
		if (s[i] == '[')
		{
			nStack[++nTop] = numTmp;
			numTmp = 0;
			lStack[++lTop] = s[i];
			continue;
		}
		if (s[i] >= '0' && s[i] <= '9')
		{
			numTmp = numTmp * 10 + s[i] - '0';
			continue;
		}
		if (s[i] != ']')
		{
			lStack[++lTop] = s[i];
			continue;
		}
		//临时字符串
		char tmpAlph[1000] = "";
		int k = 0;
		while (lTop != -1 && lStack[lTop] != '[')
		{
			tmpAlph[k++] = lStack[lTop--];
		}
		//将'['出栈, 同时注意栈中数据为逆序，需要反转
		lTop--;
		reverse(tmpAlph);
		//重复次数
		int times = nStack[nTop--];
		for (int t = 0; t < times; t++)
		{
			for (int j = 0; j < k; j++)
			{
				//组合times次数的字符串
				lStack[++lTop] = tmpAlph[j];
			}
		}
	}
	char* ans = (char*)calloc(sizeof(char), L_MAX_SIZE);
	// 注意不能直接strcpy，因为lStack可能不只是答案，因为lTop中间的值可能是++又--过了// 因此，有效字符应为存储在lStack中，长度为lTop + 1的字符串
	memcpy(ans, lStack, sizeof(char) * (lTop + 1));